% Properties equality (dictionaries).
:- op(300, xfx, '==').

% Auxiliary string operators.

:- op(300, xfx, endsWith).

%X endsWith Y :- 

:- op(1100, xfx, '-->').
:- op(1100, xfx, ':=').

conditions(C) :- cond(C).
conditions([A-->B]) :- conditions(A-->B).
conditions([A:=B]) :- conditions(A:=B). 

% tuProlog does not have the predicate sort defined
% sort(Raw, Sorted) :- quicksort(Raw, '@<', Sorted).
sort(List, Sorted) :- is_sorted(List), !, List=Sorted.
sort(List, Sorted) :- merge_sort(List, Sorted).

is_sorted([]).
is_sorted([Elem]).
is_sorted([A | [B | Tail]]) :- (A @< B), is_sorted([B | Tail]).

merge_sort([], []).
merge_sort([Elem], [Elem]).
merge_sort([A | [B | Tail]], Sorted) :-
  split([A | [B | Tail]], L, R),
  merge_sort(L, SL),
  merge_sort(R, SR),
  merge(SL, SR, Sorted).

merge([], R, R).
merge([Head | Tail], [], [Head | Tail]).
merge([Head | LTail], [Head | RTail], [Head | [Head | Tail]]) :-
  merge(LTail, RTail, Tail).
merge([LHead | LTail], [RHead | RTail], [LHead | Tail]) :-
  (LHead @< RHead), merge(LTail, [RHead | RTail], Tail).
merge([LHead | LTail], [RHead | RTail], [RHead | Tail]) :-
  (LHead @> RHead), merge([LHead | LTail], RTail, Tail).

split([], [], []).
split([Head | Tail], [Head | LTail], RTail) :-
  split(Tail, RTail, LTail).

nlpat_solve(Result) :- 
  conditions(Conditions),
  nlpat_concretize(Literals, DictionaryIndices),
  append(Conditions, Literals, MergedConditions),
  nlpat_splc(MergedConditions, SplitConditions),
  nlpat_solve(SplitConditions, DictionaryIndices, Solution),
  sort(Solution, SortedSolution),
  nlpat_simplify_features(SortedSolution, Result).

nlpat_solve(Conditions, DictionaryIndices, Solution) :-
  nlpat_find_vars(Conditions, Variables),
  nlpat_solve(Variables, Conditions, DictionaryIndices, Solution).
  
nlpat_solve(Variables, Conditions, DictionaryIndices, Solution) :-
  nlpat_proposed_solution(Variables, DictionaryIndices, PS),
  sort(Conditions, SortedConditions),
  sort(PS, SortedPS),
  nlpat_merge_conditions(SortedConditions, SortedPS, Solution).
  
nlpat_splc(Conditions, SplitConditions) :- 
  sort(Conditions, SortedConditions), 
  nlpat_splc_s(SortedConditions, SplitConditions).
  
nlpat_splc_s([], []).
nlpat_splc_s([F := V1 | [F := V2 | Tail]], Simplified) :-
  !, V1 = V2, ST = [F := V1 | Tail], nlpat_splc_s(ST, Simplified).
nlpat_splc_s([Head | Tail], [Head | SimplifiedTail]) :- nlpat_splc_s(Tail, SimplifiedTail).
  
nlpat_find_vars([], []).
nlpat_find_vars([Variable --> _ | Tail], [Variable | VT]) :- nlpat_find_vars(Tail, VT).
nlpat_find_vars([(A := B) | Tail], [(A := B) | VT]) :- nlpat_find_vars(Tail, VT).

nlpat_proposed_solution([], _, []).
nlpat_proposed_solution([Variable | Tail], DictionaryIndices, [s(Variable, Ort, SimplifiedFeatures) | ST]) :- 
  member(Variable := DictionaryIndex, DictionaryIndices), 
  item(DictionaryIndex, Ort, Features),
  sort(Features, SortedFeatures),
  nlpat_simplify_features(SortedFeatures, SimplifiedFeatures),
  nlpat_proposed_solution(Tail, DictionaryIndices, ST).
nlpat_proposed_solution([(Variable := Ort) | Tail], DictionaryIndices, [s(Variable, Ort, []) | ST]) :-
  nlpat_proposed_solution(Tail, DictionaryIndices, ST).

nlpat_merge_conditions([], [], []).
nlpat_merge_conditions([], [s(Variable, Ort, _) | Tail], [(Variable == Ort) | ST]) :- 
  nlpat_merge_conditions([], Tail, ST).
nlpat_merge_conditions([Variable --> Features | Tail], PS, Solution) :- 
  sort(Features, SortedFeatures),
  nlpat_simplify_features(SortedFeatures, SimplifiedFeatures),
  nlpat_merge_single_condition(Variable --> SimplifiedFeatures, PS),
  nlpat_merge_conditions(Tail, PS, Solution).
nlpat_merge_conditions([(_ := _) | Tail], PS, Solution) :- nlpat_merge_conditions(Tail, PS, Solution).

nlpat_merge_single_condition(Variable --> Features1, [s(Variable, _, Features2) | _]) :- 
  !, nlpat_unify_features(Features1, Features2). 
nlpat_merge_single_condition(SingleCondition, [_ | Tail]) :- nlpat_merge_single_condition(SingleCondition, Tail).

nlpat_simplify_features([], []).
nlpat_simplify_features([F == V1 | [F == V2 | Tail]], Simplified) :-
  !, V1 = V2, ST = [F == V1 | Tail], nlpat_simplify_features(ST, Simplified).
nlpat_simplify_features([Head | Tail], [Head | SimplifiedTail]) :- nlpat_simplify_features(Tail, SimplifiedTail).

nlpat_unify_features([], _).
nlpat_unify_features([_ | _], []).
nlpat_unify_features([Head | TL], [Head | TR]) :- nlpat_unify_features(TL, TR).
nlpat_unify_features([(FL == _) | TL], [(FR == VR) | TR]) :- FL @< FR, nlpat_unify_features(TL, [(FR == VR) | TR]). 
nlpat_unify_features([(FL == VL) | TL], [(FR == _) | TR]) :- FL @> FR, nlpat_unify_features([(FL == VL) | TL], TR).
